public class MyHashBuck {
    //每个节点
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] arr;
    public int useSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public MyHashBuck() {
        arr = new Node[10];
    }

    public void put(int key,int val) {
        int index=key%arr.length;
        Node cur=arr[index];
        while (cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //遍历完成都没有相同的元素，那么就头插
        Node node=new Node(key,val);
        node.next=arr[index];
        arr[index]=node;
        useSize++;
        if(useSize*1.0f / arr.length>DEFAULT_LOAD_FACTOR){
            //负载因子大于0.75就扩容
            //array = Arrays.copyOf(array,2*array.length);不能这样写，因为扩容后11可能就不在1的位置，而在11的位置，所以要重新求位置
            resize();
        }

    }

    public void resize() {
        Node[] newarr=new Node[2*arr.length];
        for (int i=0;i<arr.length;i++){
            Node cur=arr[i];
            while (cur!=null){
                Node tmp=cur;
                int newindex=cur.key/newarr.length;
                cur.next=newarr[newindex];
                cur=tmp.next;
            }
        }
        arr=newarr;
    }
    public int get(int key) {
        int index=key%arr.length;
        Node cur=arr[index];
        while (cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }
}
